#include "HeapSort.h"
//#include "CIndexMaxHeap.h"
//#include "MergeSort.h"
#include "QuickSort.h"
#include "SortTestHelper.h"
#include <stdlib.h>
#include <ctime>
int main(int argc, char *argv[])
{
    /****************** Heap realize ************/
    MaxHeap<int> maxheap = MaxHeap<int>(100);
    cout<<maxheap.size()<<endl;
    srand(time(NULL));
    for(int i=0; i<15; i++)
        maxheap.insert(rand()%100);

    //maxheap.testPrint();
    while(!maxheap.isEmpty())
        cout<<maxheap.extractMax()<<endl;
    /********************Heap Sort****************/
    int n = 100000;
    int* arr = SortTestHelper::generateRandomArray(n, 0, n);
    //int* arr = SortTestHelper::generateNearlyOderedArray(n, 100);
    int* arr2 = SortTestHelper::copyArray(arr, n);
    int* arr3 = SortTestHelper::copyArray(arr, n);
    SortTestHelper::testSort("Heap Sort", heapSort, arr, n);
    SortTestHelper::testSort("Heap Sort1", heapSort1, arr2, n);
    SortTestHelper::testSort("Heap Sort2", heapSort2, arr3, n);
    delete[] arr;
    delete[] arr2;
    delete[] arr3;

    cout<<"Nearly ordered test"<<endl;
    int swapTimes = 100;
    arr = SortTestHelper::generateNearlyOderedArray(n, swapTimes);
    arr2 = SortTestHelper::copyArray(arr, n);
    arr3 = SortTestHelper::copyArray(arr, n);
    SortTestHelper::testSort("Heap Sort", heapSort, arr, n);
    SortTestHelper::testSort("Heap Sort1", heapSort1, arr2, n);
    SortTestHelper::testSort("Heap Sort2", heapSort2, arr3, n);
    delete[] arr;
    delete[] arr2;
    delete[] arr3;
    /***********************Index Heap********************/

    int* arr4 = new int[n];
    for( int i = 0 ; i < n ; i ++ )
        arr4[i] = rand()%n;
    SortTestHelper::testSort("Heap Sort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n);
    delete[] arr4;
    return 0;
}
